package cs271.examples.binarytrees;
import java.util.*;

/**
 * Modification of the code at:
 * http://www.mhhe.com/engcs/compsci/collins/source_code/ch10/BinarySearchTreeMain/
 */
public class BinarySearchTree extends AbstractSet<Object> {
	protected BinaryTreeElement root;

	protected int size;


	/**
	 *  Initializes this BinarySearchTree object to be empty, to contain only elements
	 *  of type E, to be ordered by the Comparable interface, and to contain no 
	 *  duplicate elements.
	 *
	 */ 
	public BinarySearchTree() {
		root = null;
		size = 0;
	} // default constructor


	/**
	 * Initializes this BinarySearchTree object to contain a shallow copy of
	 * a specified BinarySearchTree object.
	 * The worstTime(n) is O(n), where n is the number of elements in the
	 * specified BinarySearchTree object.
	 *
	 * @param otherTree - the specified BinarySearchTree object that this
	 *                BinarySearchTree object will be assigned a shallow copy of.
	 *
	 */
	public BinarySearchTree (BinarySearchTree otherTree) {
		root = null;
		size = 0;
		for (Object element : otherTree)
			add (element);
	} // copy constructor


	/**
	 *  Returns the size of this BinarySearchTree object.
	 *
	 * @return the size of this BinarySearchTree object.
	 *
	 */
	public int size() {
		return size;
	} // method size()


	/**
	 *  Returns an iterator positioned at the smallest element in this 
	 *  BinarySearchTree object.
	 *
	 *  @return an iterator positioned at the smallest element in this
	 *                BinarySearchTree object.
	 *
	 */
	public Iterator<Object> iterator() {
		return new TreeIterator();
	} // method iterator


	/**
	 *  Determines if there is at least one element in this BinarySearchTree object that
	 *  equals a specified element.
	 *  The worstTime(n) is O(n) and averageTime(n) is O(log n).  Note that it is legal
	 *  for the specified element to be null.
	 *
	 *  @param obj - the element sought in this BinarySearchTree object.
	 *
	 *  @return true - if there is an element in this BinarySearchTree object that
	 *                equals obj; otherwise, return false.
	 *
	 *  @throws ClassCastException - if obj cannot be compared to the 
	 *  elements in this BinarySearchTree object. 
	 *  @throws NullPointerException - if obj is null.
	 *  
	 */ 
	public boolean contains(Object obj){
		return (getEntry (obj) != null);
	} // method contains



	/**
	 *  Ensures that this BinarySearchTree object contains a specified element.
	 *  The worstTime(n) is O(n) and averageTime(n) is O(log n).
	 *
	 *  @param element - the element whose presence is ensured in this 
	 *                 BinarySearchTree object.
	 *
	 *  @return true - if this BinarySearchTree object changed as a result of this
	 *                method call (that is, if element was actually inserted); otherwise,
	 *                return false.
	 *
	 *  @throws ClassCastException - if element cannot be compared to the 
	 *                  elements already in this BinarySearchTree object.
	 *  @throws NullPointerException - if element is null.
	 *
	 */
	@SuppressWarnings("unchecked")
	public boolean add(Object element) {        
		if (root == null) {
			root = new BinaryTreeElement (element, null);
			size++;
			return true;
		} else {
			BinaryTreeElement temp = root;

			int comp;

			while (true) {
				comp =  ((Comparable) element).compareTo(temp.element);
				if (comp == 0)
					return false;
				if (comp < 0)
					if (temp.getLeft() != null)
						temp = temp.getLeft();
					else {
						temp.setLeft(new BinaryTreeElement (element, temp));
						size++;
						return true;
					} else if (temp.getRight() != null)
						temp = temp.getRight();
					else {
						temp.setRight(new BinaryTreeElement (element, temp));
						size++;
						return true;
					} // temp.right == null
			} // while
		} // root not null
	} // method add


	/**
	 *  Ensures that this BinarySearchTree object does not contain a specified 
	 *  element.
	 *  The worstTime(n) is O(n) and averageTime(n) is O(log n).
	 *
	 *  @param obj - the object whose absence is ensured in this 
	 *                 BinarySearchTree object.
	 *
	 *  @return true - if this BinarySearchTree object changed as a result of this
	 *                method call (that is, if obj was actually removed); otherwise,
	 *                return false.
	 *
	 *  @throws ClassCastException - if obj cannot be compared to the 
	 *                  elements in this BinarySearchTree object. 
	 *  @throws NullPointerException - if obj is null.
	 *
	 */
	public boolean remove(Object obj) {
		BinaryTreeElement e = getEntry(obj);
		if (e == null)
			return false;
		deleteEntry (e);
		return true;
	} // method remove


	/**
	 *  Finds the Entry object that houses a specified element, if there is such an Entry.
	 *  The worstTime(n) is O(n), and averageTime(n) is O(log n).
	 *
	 *  @param obj - the element whose Entry is sought.
	 *
	 *  @return the Entry object that houses obj - if there is such an Entry;
	 *                otherwise, return null.  
	 *
	 *  @throws ClassCastException - if obj is not comparable to the elements
	 *                  already in this BinarySearchTree object.
	 *  @throws NullPointerException - if obj is null.
	 *
	 */
	@SuppressWarnings("unchecked")
	protected BinaryTreeElement getEntry(Object obj) {
		int comp;

		BinaryTreeElement e = root;
		while (e != null) 
		{
			comp = ((Comparable) obj).compareTo(e.element);
			if (comp == 0)
				return e;
			else if (comp < 0)
				e = e.getLeft();
			else
				e = e.getRight();
		} // while
			return null;
	} // method getEntry

	/**
	 *  Deletes the element in a specified Entry object from this BinarySearchTree.
	 *  
	 *  @param p - the Entry object whose element is to be deleted from this
	 *                 BinarySearchTree object.
	 *
	 *  @return the Entry object that was actually deleted from this BinarySearchTree
	 *                object. 
	 *
	 */
	protected BinaryTreeElement deleteEntry(BinaryTreeElement p) {
		size--;

		// If p has two children, replace p's element with p's successor's
		// element, then make p reference that successor.
		if (p.getLeft() != null && p.getRight() != null) {
			BinaryTreeElement s = successor (p);
			p.element = s.element;
			p = s;
		} // p had two children


		// At this point, p has either no children or one child.

		BinaryTreeElement replacement;

		if (p.getLeft() != null)
			replacement = p.getLeft();
		else
			replacement = p.getRight();

		// If p has at least one child, link replacement to p.parent.
		if (replacement != null) {
			replacement.setParent(p.getParent());
			if (p.getParent() == null)
				root = replacement;
			else if (p == p.getParent().getLeft())
				p.getParent().setLeft(replacement);
			else
				p.getParent().setRight(replacement);
		} // p has at least one child  
		else if (p.getParent() == null)
			root = null;
		else 
		{
			if (p == p.getParent().getLeft())
				p.getParent().setLeft(null);
			else
				p.getParent().setRight(null);        
		} // p has a parent but no children
		return p;
	} // method deleteEntry


	/**
	 *  Finds the successor of a specified Entry object in this BinarySearchTree.
	 *  The worstTime(n) is O(n) and averageTime(n) is constant.
	 *
	 *  @param e - the Entry object whose successor is to be found.
	 *
	 *  @return the successor of e, if e has a successor; otherwise, return null.
	 *
	 */
	protected BinaryTreeElement successor (BinaryTreeElement e) 
	{
		if (e == null)
			return null;
		else if (e.getRight() != null) 
		{
			// successor is leftmost Entry in right subtree of e
			BinaryTreeElement p = e.getRight();
			while (p.getLeft() != null)
				p = p.getLeft();
			return p;
		} // e has a right child
		else 
		{

			// go up the tree to the left as far as possible, then go up
			// to the right.
			BinaryTreeElement p = e.getParent();
			BinaryTreeElement child = e;
			while (p != null && child == p.getRight()) 
			{
				child = p;
				p = p.getParent();
			} // while
				return p;
		} // e has no right child
	} // method successor


	protected class TreeIterator implements Iterator<Object>
	{
		protected BinaryTreeElement lastReturned = null,
		next;

		/**
		 *  Positions this TreeIterator to the smallest element, according to the Comparable
		 *  interface, in the BinarySearchTree object.
		 *  The worstTime(n) is O(n) and averageTime(n) is O(log n).
		 *
		 */
		protected TreeIterator() 
		{
			next = root;
			if (next != null)
				while (next.getLeft() != null)
					next = next.getLeft();
		} // default constructor


		/**
		 *  Determines if there are still some elements, in the BinarySearchTree object this
		 *  TreeIterator object is iterating over, that have not been accessed by this
		 *  TreeIterator object.
		 *
		 *  @return true - if there are still some elements that have not been accessed by
		 *                this TreeIterator object; otherwise, return false.
		 *
		 */ 
		public boolean hasNext() 
		{
			return next != null;
		} // method hasNext


		/**
		 *  Returns the element in the Entry this TreeIterator object was positioned at 
		 *  before this call, and advances this TreeIterator object.
		 *  The worstTime(n) is O(n) and averageTime(n) is constant.
		 *
		 *  @return the element this TreeIterator object was positioned at before this call.
		 *
		 *  @throws NoSuchElementException - if this TreeIterator object was not 
		 *                 positioned at an Entry before this call.
		 *
		 */
		public Object next() 
		{
			if (next == null)
				throw new NoSuchElementException();
			lastReturned = next;
			next = successor (next);
			return lastReturned.element;
		} // method next


		/**
		 *  Removes the element returned by the most recent call to this TreeIterator
		 *  object�s next() method.
		 *  The worstTime(n) is O(n) and averageTime(n) is constant.
		 *
		 *  @throws IllegalStateException - if this TreeIterator�s next() method was not
		 *                called before this call, or if this TreeIterator�s remove() method was
		 *                called between the call to the next() method and this call.
		 *
		 */ 
		public void remove() 
		{
			if (lastReturned == null)
				throw new IllegalStateException();
			if (lastReturned.getLeft() != null && lastReturned.getRight() != null)
				next = lastReturned;
			deleteEntry(lastReturned);
			lastReturned = null;
		} // method remove     

	} // class TreeIterator
	
	public static void main(String[] args) {
		BinarySearchTree tree1 = new BinarySearchTree();

		tree1.add ("yes");
		tree1.add ("no");
		tree1.add ("maybe");
		tree1.add ("always");
		tree1.add ("no");   // not added: duplicate element
		System.out.println (tree1);
		if (tree1.remove ("often"))
			System.out.println ("How did that happen?");
		else
			System.out.println (tree1.remove ("maybe"));
		System.out.println (tree1);   
	}



} // class BinarySearchTree
